package personal.leil.learning.heap;

import personal.leil.learning.utils.ArrayUtils;

import java.util.PriorityQueue;

/**
 * 堆排序拓展题目
 * <p>
 * 已知一个几乎有序的数组，几乎有序是指，
 * 如果把数组拍好顺序的话，每个元素移动的距离可以不超过k，
 * 并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-11
 */
public class HeapSortExtend {


    /**
     * 代码实现
     * <p>
     * 借助一个长度为k的小根堆，辅助数组进行排序
     * </p>
     *
     * @param arr source array
     */
    public static void process(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        /*
        将前k+1个数添加到优先级队列（小根堆），则整个数组的最小值为小根堆的根节点
         */
        int i = 0;
        for (; i <= Math.min(arr.length, k); i++) {
            heap.add(arr[i]);
        }
        /*
        弹出最小值
        将新的值添加到小根堆中
         */
        int j = 0;
        for (; i < arr.length; i++, j++) {
            heap.add(arr[i]);
            arr[j] = heap.poll();
        }
        while (!heap.isEmpty()) {
            arr[j++] = heap.poll();
        }
    }


    /********************* For Test *************************/


    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 4, 6, 5, 9, 8};
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        process(arr, 3);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }


}
